package algotithm.leetcode.stack.test739;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author 25068
 * @Date 2021/5/18 23:00
 * @Title 739. 每日温度
 */
public class Solution {

    public static void main(String[] args) {
        int[] t = {73, 74, 75, 71, 69, 72, 76, 73};
        Solution solution = new Solution();
        int[] temperatures = solution.dailyTemperatures(t);
        for (int temp : temperatures) {
            System.out.print(temp + " ");
        }
    }

    public int[] dailyTemperatures(int[] T) {
        int length = T.length;
        int[] ans = new int[length];
        int prevIndex = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < length; i++) {
            int temperature = T[i];
            while (!stack.isEmpty() && temperature > T[stack.peek()]) {
                prevIndex = stack.pop();
                ans[prevIndex] = i - prevIndex;
            }
            stack.push(i);
        }
        return ans;
    }
}
